package com.ds.bintree.LeetCode;

import java.util.LinkedList;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/9/21 14:22
 */
public class TreeTraversalCommon2 {
    public void LRN(TreeNode root) {
        LinkedList<TreeNode> s = new LinkedList<>();
        TreeNode t = root;
        TreeNode r = null; //记录上次访问过的节点
        //当t指针为空，而且堆栈也为空的时候遍历就结束了
        while (t!=null || !s.isEmpty()){
            //每次当t不为空的时候就默认把t压入堆栈
            if (t!=null){
                s.addFirst(t);
                t = t.left;
            } else {
                t = s.getFirst();
                if (t.right!=null && r != t.right){
                    //该节点的右孩子不空，而且上一个访问的不是右孩子(证明这是从左孩子回溯过来的)
                    t = t.right;
                } else {
                    //该节点的右孩子为空，或者右孩子已经访问过了
                    t = s.removeFirst();
                    System.out.println(t);  //遍历节点
                    r = t;
                    t = null; //防止t被压入堆栈，所以要置空
                }
            }
        }
    }

    public void NLR(TreeNode root) {
        LinkedList<TreeNode> s = new LinkedList<>();
        TreeNode t = root;
        //当t指针为空，而且堆栈也为空的时候遍历就结束了
        while (t!=null || !s.isEmpty()){
            //每次当t不为空的时候就默认把t压入堆栈
            if (t!=null){
                System.out.println(t); //遍历节点
                s.addFirst(t);
                t = t.left;
            } else {
                t = s.removeFirst();
                t = t.right;
            }
        }
    }

    public void LNR(TreeNode root) {
        LinkedList<TreeNode> s = new LinkedList<>();
        TreeNode t = root;
        //当t指针为空，而且堆栈也为空的时候遍历就结束了
        while (t!=null || !s.isEmpty()){
            //每次当t不为空的时候就默认把t压入堆栈
            if (t!=null){
                s.addFirst(t);
                t = t.left;
            } else {
                t = s.removeFirst();
                System.out.println(t); //遍历节点
                t = t.right;
            }
        }
    }
}
